package tree;

/**
 * 给你一棵 n 个节点的 无向 树，节点从 0 到 n - 1 编号。树以长度为 n - 1 下标从 0 开始的二维整数数组 edges 的形式给你，其中
 * edges[i] = [ui, vi] 表示树中节点 ui 和 vi 之间有一条边。同时给你一个 正 整数 k 和一个长度为 n 下标从 0 开始的 非负 整数数组
 * nums ，其中 nums[i] 表示节点 i 的 价值 。
 * <p>
 * Alice 想 最大化 树中所有节点价值之和。为了实现这一目标，Alice 可以执行以下操作 任意 次（包括 0 次）：
 * 选择连接节点 u 和 v 的边 [u, v] ，并将它们的值更新为：
 * nums[u] = nums[u] XOR k
 * nums[v] = nums[v] XOR k
 * 请你返回 Alice 通过执行以上操作 任意次 后，可以得到所有节点 价值之和 的 最大值 。
 * <p>
 * 示例 1：
 * 输入：nums = [1,2,1], k = 3, edges = [[0,1],[0,2]]
 * 输出：6
 * 解释：Alice 可以通过一次操作得到最大价值和 6 ：
 * - 选择边 [0,2] 。nums[0] 和 nums[2] 都变为：1 XOR 3 = 2 ，数组 nums 变为：[1,2,1] -> [2,2,2] 。
 * 所有节点价值之和为 2 + 2 + 2 = 6 。
 * 6 是可以得到最大的价值之和。
 * <p>
 * 示例 2：
 * 输入：nums = [2,3], k = 7, edges = [[0,1]]
 * 输出：9
 * 解释：Alice 可以通过一次操作得到最大和 9 ：
 * - 选择边 [0,1] 。nums[0] 变为：2 XOR 7 = 5 ，nums[1] 变为：3 XOR 7 = 4 ，数组 nums 变为：[2,3] -> [5,4] 。
 * 所有节点价值之和为 5 + 4 = 9 。
 * 9 是可以得到最大的价值之和。
 * <p>
 * 示例 3：
 * 输入：nums = [7,7,7,7,7,7], k = 3, edges = [[0,1],[0,2],[0,3],[0,4],[0,5]]
 * 输出：42
 * 解释：Alice 不需要执行任何操作，就可以得到最大价值之和 42 。
 *
 * @author Jisheng Huang
 * @version 20250523
 */
public class MaximumSumValue_3068 {
    /**
     * @param nums  the given integer array
     * @param k     the given integer
     * @param edges the given edges array
     * @return the maximum value sum
     */
    public static long maximumValueSum(int[] nums, int k, int[][] edges) {
        long dp0 = 0;
        long dp1 = Long.MIN_VALUE / 10;

        for (int num : nums) {
            long a = Math.max(dp0 + num, dp1 + (num ^ k));
            long b = Math.max(dp0 + (num ^ k), dp1 + num);
            dp0 = a;
            dp1 = b;
        }

        return dp0;
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 1};
        int k = 3;
        int[][] edges = {{0, 1}, {0, 2}};

        System.out.println(maximumValueSum(nums, k, edges));
    }
}
